package _4lists.src.Deque;
/**
 * 基于环形链表的双端队列
 * @param <E> 元素类型
 */
//注意：在这个过程中，哨兵节点的位置是不会进行改变的(正常情况下也不会发生改变)
public class LinkedListDeque<E>  {

    //a(哨兵) offered b(若是添加的第一个，那么b也是哨兵，否则就是a.next;)

    public boolean offerFirst(E e) {
        if (isFull()) {
            return false;
        }
        size++;//注意进行链表实际长度的增加
        Node<E> a = sentinel;
        Node<E> b = sentinel.next;
        //记住，双向链表一般要进行四次指针的交换
        Node<E> offered = new Node<>(a, e, b);//交换两次
        a.next = offered;
        b.prev = offered;
        return true;
    }
    //尾节点a=哨兵.prev(这是一个依靠环形链表形成的队列，根据形成的原理可以直接揭晓，哨兵的prev就是尾节点)，注意哨兵节点的位置没有发生改变

    public boolean offerLast(E e) {
        if (isFull()) {
            return false;
        }
        size++;//注意进行链表实际长度的增加
        Node<E> a = sentinel.prev;
        Node<E> b = sentinel;
        Node<E> offered = new Node<>(a, e, b);//依旧要进行四次指针的交换
        a.next = offered;
        b.prev = offered;
        return true;
    }

    //由于要移除头节点，我们需要找到哨兵，哨兵的next就是头节点，我们还需要找到头节点下的下一个节点，为的是下面就行移除头节点后链表的完整
    public E pollFirst() {
        if (isEmpty()) {
            return null;
        }
        Node<E> a = sentinel;
        Node<E> polled = sentinel.next;//这个就是头节点
        Node<E> b = polled.next;//头节点的下一个节点
        a.next = b;//进行链表的完整性的修改
        b.prev = a;
        size--;//注意进行链表实际长度的减少
        return polled.value;
    }


    public E pollLast() {
        if (isEmpty()) {
            return null;
        }
        Node<E> polled = sentinel.prev;//找到链表的尾节点
        Node<E> a = polled.prev;//找到尾节点前的哪一个节点
        Node<E> b = sentinel;
        a.next = b;//进行链表的完整性的修改
        b.prev = a;
        size--;//注意进行链表实际长度的减少
        return polled.value;
    }


    public E peekFirst() {
        if (isEmpty()) {
            return null;
        }
        return sentinel.next.value;//看前面的pollFirst即可
    }


    public E peekLast() {
        if (isEmpty()) {
            return null;
        }
        return sentinel.prev.value;//看前面的pollLast即可
    }


    public boolean isEmpty() {
        return size == 0;//根据实际容量的大小进行比较
    }


    public boolean isFull() {
        return size == capacity;//根据实际容量和宗容量进行比较
    }



    static class Node<E> {
        Node<E> prev;
        E value;
        Node<E> next;

        public Node(Node<E> prev, E value, Node<E> next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    Node<E> sentinel = new Node<>(null, null, null);
    int capacity;
    int size;

    public LinkedListDeque(int capacity) {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
        this.capacity = capacity;
    }//初始化容量时，顺便将其形成一个环状链表的结构
}
